/LMAR=0/XLINE=3/FONT#0=BASL30/FONT#1=BASI30/FONT#2=BASB30/FONT#3=STA200/FONT#4=NGB25
␈↓ ↓H␈↓␈↓βS␈↓∧ Artificial Intelligence Laboratory, STANFORD UNIVERSITY, Stanford, California 94305

␈↓ ↓H␈↓∧Telephone 415 497-4430␈↓ 
≤May 27, 1977 




␈↓ ↓H␈↓Dr. Calvin C. Elgot
␈↓ ↓H␈↓Thomas J. Watson Research Center
␈↓ ↓H␈↓Yorktown Heights, N.Y. 10598

␈↓ ↓H␈↓Dear Calvin:

␈↓ ↓H␈↓        Thanks␈α
for␈α
your␈α∞␈↓↓On␈α
the␈α
Many␈α
Facets␈α∞of␈α
Lists␈↓.␈α
 You␈α
may␈α∞be␈α
interested␈α
in␈α
two␈α∞related␈α
old
␈↓ ↓H␈↓papers␈α∞of␈α∞mine:␈α∞␈↓↓A␈α∞Basis␈α∞for␈α∞a␈α∞Mathematical␈α∞Theory␈α∞of␈α∞Computation␈↓␈α∞in␈α∞Bra≥ort␈α∞and␈α∞Hirschberg
␈↓ ↓H␈↓␈↓↓Computer␈α∞Programming␈α∞and␈α∞Formal␈α∞Systems␈↓␈α∞North-Holland␈α∞1963,␈α∞and␈α∞␈↓↓Towards␈α∂a␈α∞Mathematical
␈↓ ↓H␈↓↓Science␈α∂of␈α⊂Computation␈↓␈α∂in␈α⊂the␈α∂Proceedings␈α∂of␈α⊂the␈α∂1962␈α⊂IFIP␈α∂congress.␈α∂ In␈α⊂the␈α∂former␈α⊂paper,␈α∂I
␈↓ ↓H␈↓discuss␈α
the␈α
formal␈αdescription␈α
of␈α
recursive␈αdata␈α
structures␈α
including␈αlists␈α
and␈α
S-expressions,␈αand␈α
in
␈↓ ↓H␈↓the␈α⊂latter,␈α⊂I␈α⊂introduce␈α∂the␈α⊂idea␈α⊂of␈α⊂␈↓↓abstract␈α∂syntax␈↓␈α⊂which␈α⊂is␈α⊂related␈α∂-␈α⊂though␈α⊂I␈α⊂don't␈α⊂make␈α∂the
␈↓ ↓H␈↓connection.␈α∞ The␈α∞idea␈α∞of␈α∞recursive␈α∞de≡nitions␈α∞of␈α∞data␈α∞structures␈α∞was␈α∞re-invented␈α∞by␈α∞Hoare␈α∞in␈α∞a
␈↓ ↓H␈↓1973 paper.  The ≡rst paper also discusses the related injections and projections.


␈↓ ↓H␈↓Best regards,



␈↓ ↓H␈↓John McCarthy
␈↓ ↓H␈↓Director
␈↓ ↓H␈↓Professor of Computer Science